package com.java.learn;
/*Interview Question: find the all possible combination of digits ranging 1 to 9 whose sum is 10
no digit shud be repeated in any combination.
1234
127
136
145
19
235
28
37
46*/

import java.util.Arrays;
import java.util.LinkedList;

public class Subset {

int myarray[];
int sum = 0;
int findnumber;
LinkedList<Integer> list = new LinkedList<>();

public Subset(int myarr[], int findnumber) {
this.myarray = myarr;
this.findnumber = findnumber;
}

public void subset(int startingValue) {

for (int i = startingValue; i < myarray.length; i++) {

sum = sum + myarray[i];

if(sum > findnumber){
sum = sum - myarray[i];
break;
}

list.add(myarray[i]);

subset(i+1);

sum = sum - myarray[i];
list.removeLast();

}


if(sum == findnumber){
System.out.println(list+" == "+sum);
}

}

public static void main(String[] args) {

int myarray[] = { 1, 2, 3, 4, 5,6,7,8,9 };
int findnumber = 10;
Arrays.sort(myarray);
Subset sub = new Subset(myarray, findnumber);
sub.subset(0);

}

} 
